package com.itzmn.newcode.offer1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @Author: 张梦楠
 * @Date: 2018/12/19 15:00
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description:
 */
public class Tree {

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

    /**
     * 先序遍历，先输出根，再左再右。递归实现，
     * @param root
     */
    public void PreorderTraversal(TreeNode root){

        System.out.print(root.val+" ");

        if (root.left != null){
            PreorderTraversal(root.left);
        }
        if (root.right != null){
            PreorderTraversal(root.right);
        }
    }

    /**
     * 先序遍历，非递归版本
     * @param root
     */
    public void PreorderTraversalNonRecu(TreeNode root){
        if (root != null){
            Stack<TreeNode> stack = new Stack<>();
            // 先序，先输出根，在输出左，在输出右，所以先压右子树，在压左子树
            stack.push(root);
            while (!stack.isEmpty()){
                root = stack.pop();
                System.out.print(root.val+" ");
                if (root.right != null){
                    stack.push(root.right);
                }
                if (root.left != null){
                    stack.push(root.left);
                }
            }
        }
        System.out.println();
    }

    /**
     * 中序遍历，先左再根，在右。递归实现，
     * @param root
     */
    public void InOrderTraversal(TreeNode root){

        if (root.left != null){
            InOrderTraversal(root.left);
        }
        System.out.print(root.val+" ");
        if (root.right != null){
            InOrderTraversal(root.right);
        }

    }


    /**
     * 中序遍历，非递归
     * @param root
     */
    public void InOrderTraversalNonRecu(TreeNode root){
        if (root != null){
            Stack<TreeNode> stack = new Stack<>();
            // 中序遍历，先输出左节点，输出根，输出右子树，所以先压最左子树，在压右子树
            while (!stack.isEmpty() || root != null){
                // 如果还没走到最左。一直赋值左节点
                if (root != null){
                    stack.push(root);
                    root = root.left;
                }else {
                    // 如果抵达了最左，那么弹出父亲，输出，然后赋值右子树
                    root = stack.pop();
                    System.out.print(root.val+" ");
                    root = root.right;
                }
            }
        }
    }
    /**
     * 后序遍历，递归实现，
     * @param root
     */
    public void PostOrderTraversal(TreeNode root){
        if (root.left != null){
            PostOrderTraversal(root.left);
        }

        if (root.right != null){
            PostOrderTraversal(root.right);
        }
        System.out.print(root.val+" ");
    }

    /**
     * 后序遍历，非递归
     * @param root
     */
    public void PostOrderTraversalNonRecu(TreeNode root){

        // 后序遍历，先左，再右，再根，使用两个栈，先按照根，右，左，遍历节点，然后将值逆序
        // 存放节点
        Stack<TreeNode> s1 = new Stack<>();
        // 存放值
        Stack<TreeNode> s2 = new Stack<>();
        s1.push(root);
        while (!s1.isEmpty()){
            root = s1.pop();
            s2.push(root);
            if (root.left != null){
                s1.push(root.left);
            }
            if (root.right != null){
                s1.push(root.right);
            }
        }
        while (!s2.isEmpty()){
            System.out.print(s2.pop().val + " ");
        }
    }

    /**
     * 层序遍历，按照树的每一层遍历，使用队列
     */
    public void SequenceTraversal(TreeNode root){

        //层序遍历队列，先入先出,出来节点，进入左右子树
        LinkedList<TreeNode> treeNodes = new LinkedList<>();
        treeNodes.add(root);
        while (!treeNodes.isEmpty()){
            TreeNode treeNode = treeNodes.removeFirst();
            System.out.print(treeNode.val+" ");
            if (treeNode.left != null){
                treeNodes.add(treeNode.left);
            }
            if (treeNode.right != null){
                treeNodes.add(treeNode.right);
            }
        }
        System.out.println();
    }

    /**
     * 深度遍历,相当于先序遍历，采用非递归实现，
     * @param root
     */
    public void DeepTraversal(TreeNode root){

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            System.out.print(pop.val+" ");
            if (pop.right!=null){
                stack.push(pop.right);
            }
            if (pop.left != null){
                stack.push(pop.left);
            }
        }
        System.out.println();
    }

    /**
     * 创建二叉树，按层创建 有空节点，用-1表示,这个是所有空节点都被-1表示出来了，也就是空节点的子节点也被表示出来，
     * 这个数组是一个完全二叉树
     * [1,2,-1,4,5,-1,-1,8]
     *                         1
     *                    2          空
     *                4      5     空   空
     *             8
     *
     *             这种，空节点的子节点也会表示出来
     * @param arrays
     * @return
     */
    public TreeNode createBinaryTree(int[] arrays){

        ArrayList<TreeNode> treeNodes = new ArrayList<>();

        for (int i=0;i<arrays.length;i++){
            TreeNode treeNode = new TreeNode(arrays[i]);
            treeNodes.add(treeNode);
        }

        for (int i=0;i<treeNodes.size();i++){
            if (2*i+1 >= treeNodes.size() || treeNodes.get(i).val==-1){
                break;
            }
            treeNodes.get(i).left = treeNodes.get(2*i+1).val == -1? null:treeNodes.get(2*i+1);
            if (2*i+2 >= treeNodes.size()){
                break;
            }
            treeNodes.get(i).right = treeNodes.get(2*i+2).val == -1? null:treeNodes.get(2*i+2);
        }

        return treeNodes.get(0);
    }


    /**
     * 创建二叉树，有空节点，但是空节点的子节点就没有表示出来了。这个数组不是按照完全二叉树的方式
     * [8,8,-1,9,-1,2,-1,5]
     *          8
     *        8  空
     *      9  空
     *    2  空
     *  5 空
     *  这种，空节点的子节点就没有表示了
     * @param arrays
     * @return
     */
    public TreeNode createBinaryTreeWithOnlyOneNull(int[] arrays){

        // 用来存放所有的node节点
        LinkedList<TreeNode> LinkeNodes = new LinkedList<>();
        for (int i=0;i<arrays.length;i++){
            TreeNode treeNode = new TreeNode(arrays[i]);
            LinkeNodes.add(treeNode);
        }

        TreeNode root = LinkeNodes.removeFirst();
        TreeNode tempRoot = null;

        // 当前层的节点
        LinkedList<TreeNode> FloorNodes = new LinkedList<>();

        FloorNodes.add(root);
        while (!FloorNodes.isEmpty() ){

            tempRoot = FloorNodes.removeFirst();

            // 如果这个节点是-1，说明是null
            if (LinkeNodes.isEmpty()){
                break;
            }
            TreeNode leftNode = LinkeNodes.removeFirst();
            // 说明这个节点为null
            tempRoot.left = leftNode.val==-1?null:leftNode;
            // 如果左节点不是null，将这个左节点加入下一层
            if (tempRoot.left!=null){
                FloorNodes.add(tempRoot.left);
            }

            // 设置右节点
            // 如果这个节点是-1，说明是null
            if (LinkeNodes.isEmpty()){
                break;
            }
            TreeNode rightNode = LinkeNodes.removeFirst();
            // 说明这个节点为null
            tempRoot.right = rightNode.val==-1?null:rightNode;

            // 如果右节点不是null，将这个右节点加入下一层
            if (tempRoot.right!=null){
                FloorNodes.add(tempRoot.right);
            }

        }

        InOrderTraversal(root);
        return root;
    }


    /**
     * 创建二叉搜索树
     * @param arrays
     * @return
     */
    public TreeNode createBinarySearchTree(int[] arrays){

        TreeNode root = new TreeNode(arrays[0]);

        for (int i=1;i<arrays.length;i++){
            TreeNode tempRoot = root;
            create(root,new TreeNode(arrays[i]));
        }

        return root;
    }
    private void create(TreeNode root,TreeNode node){
        // 根节点大，左子树
        if (root.val > node.val){
            if (root.left!=null){
                create(root.left,node);
            }else {
                root.left = node;
            }
        }
        // 根节点小，右子树
        if (root.val <= node.val){
            if (root.right != null){
                create(root.right,node);
            }else {
                root.right = node;
            }
        }

    }

}
